import java.util.Objects;public class Solution2807 {

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static int GCD(int m, int n) {
        int result = 0;
        while (n != 0) {
            result = m % n;
            m = n;
            n = result;
        }
        return m;


    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if(Objects.isNull(head)){
            return null;
        }
        ListNode left = head, right = head.next;
        while(Objects.nonNull(left) && Objects.nonNull(right)){
            int leftNum = left.val, rightNum = right.val;
            ListNode mid = new ListNode(GCD(leftNum, rightNum));
            left.next = mid;
            mid.next = right;
            left = right;
            right = right.next;
        }
        return head;
    }
}
